package LearnAlgorithm.h_标准数学公式;

import java.util.Scanner;

/*
扩展欧几里得算法：
	gcd(a,b)的核心语句：
		return b == 0 ? a : (gcd(b,a%b))


我们观察到：欧几里德算法停止的状态是：
	a = gcd，
	b = 0，
那么，这是否能给我们求解x，y提供一种思路呢?


	a'x + b'y = gcd；此时x = 1，y为任意数
因为这时候，只要a = gcd的系数是1，那么只要b的系数是0或者其他值(无所谓是多少，反正任何数乘以0都等于0；但是a的系数一定要是1)
那么这时，我们就会有：
	a*1 + b*0 = gcd
当然这是最终状态，但是我们是否可以从最终状态反推到最初的状态呢?


假设当前我们要处理的是：
1)求出a和b的最大公约数，
2)并求出x和y使得：
	a*x + b*y= gcd (1式) 					--->要求的
而我们已经求出了下一个状态：
	b和a%b的最大公约数，
	并且求出了一组x1和y1使得：
	b*x1 + (a%b)*y1 = gcd (2式)			--->下一个状态
那么这两个相邻的状态之间是否存在一种关系呢?


我们知道：
	a%b = a - (a/b)*b (这里的“/”指的是整除，例如5/2=2，1/3=0)
那么，我们可以进一步得到：
	gcd = b*x1 + (a-(a/b)*b)*y1
		= b*x1 + a*y1 - (a/b)*b*y1
		= a*y1 + b*(x1 - a/b*y1) (3式)	--->等价于(2式)
对比之前我们的状态，也就是式(3)和式(1)，求一组x和y使得：a*x + b*y = gcd，是否发现了什么?


得：
	x = y1
	y = x1 - a/b*y1
这两个就是递推式
 */
public class f拓展欧几里得算法 {
	static double x = 0D;
	static double y = 0D;
	
	public static void main(String[] args) {
		double d = new f拓展欧几里得算法().extendedEuclideanAlgorithm(12, 42);
		System.out.println(d);
		
//		try {
//			new f拓展欧几里得算法().foolOperation();//12x + 42y = 6
//		} catch (Exception e) {
//			// TODO Auto-generated catch block
//			e.printStackTrace();
//		}
	}
	
	public void foolOperation() throws Exception {
		Scanner scanner = new Scanner(System.in);
		System.out.println("线性方程ax + by = m");
		System.out.println("其中a = ");
		double a = scanner.nextDouble();
		System.out.println("其中b = ");
		double b = scanner.nextDouble();
		System.out.println("其中m = ");
		double m = scanner.nextDouble();
		System.out.println("a与b的最大公约数：" + lineEuclideanAlgorithm(a, b, m));
		System.out.println("无数个解中的其中一对解：[" + x + ", " + y + "]");
	}
	
	/**
		线性方程ax + by = m
		当m是gcd(a, b)倍数时有解；即m % gcd(a, b) = 0时有解
		等价于ax = m mod b
	 * @param a
	 * @param b
	 * @param m
	 * @return
	 * @throws Exception
	 */
	public double lineEuclideanAlgorithm(double a, double b, double m) throws Exception {//ax + by = m
		double d = extendedEuclideanAlgorithm(a, b);
		if (m % d != 0) {
			throw new Exception("无解!");
		}
		x *= (m / d);//这里为什么*=(m / d)；是因为*=之前求出来的x，y是这个方程“ax + by = gcd(a, b)”的无数个解中的一对解
		y *= (m / d);//gcd(a, b)不一定等于m，但m一定是gcd(a, b)的倍数！多少倍？是(m / gcd(a, b))倍！
		return d;
	}
	
	/**
	 * 拓展欧几里得模板
	 * 调用完成后xy是ax+by-gcd(a, b)的解
	 * @param a
	 * @param b
	 * @return
	 */
	public double extendedEuclideanAlgorithm(double a, double b) {
		if (b == 0D) {//这里是递归出口；也就是最底下的一层的操作；此时a=gcd,b=0
			x = 1D;
			y = 0D;
			return a;
		}
		double res = extendedEuclideanAlgorithm(b, a % b);
		double x1 = x;//声明一个变量来保存上一次的x，因为下面紧接着x就会被改变了
		x = y;//将上一次得y赋值给这一次的x；也就是x = y1
		y = x1 - ((int) (a / b) * y);//将这一次的y赋值；也就是y = x1 - a/b*y1
		return res;
	}
	
	/**
	 * 初始欧几里得模板
	 * @param a
	 * @param b
	 * @return
	 */
	public double gcd(double a, double b) {
		return b == 0 ? a : gcd(b, a % b);
	}
}
